package megamu.mesh;

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.Map;

import quickhull3d.QuickHull3D;

import com.jellyfishumbrella.GL.Vertex;
import com.jellyfishumbrella.util.Trace;

public class Voronoi {
	public final double						TOO_CLOSE	= 5;
	public LinkedHashMap<String, Corner>	corners;
	// public float[][] edges;
	Region[]								regions;
	VoronoiInput<Site>						sites;
	protected Delaunay						delaunay;

	LinkedHashMap<String, Edge>				edges		= new LinkedHashMap<String, Edge>();

	public Voronoi() {

		delaunay = new Delaunay();
	}

	public void generate(VoronoiInput<Site> baseSites) {
		Trace.getCurrentMethodName();
		sites = baseSites;
		corners = new LinkedHashMap<String, Corner>();
		edges = new LinkedHashMap<String, Edge>();

		if (baseSites == null) {
			// edges = new float[0][4];
			regions = new Region[0];
			return;
		}

		// build points array for qhull
		System.out.println(baseSites.size() + "   " + (baseSites.size() * 3 + 9));
		double qPoints[] = new double[baseSites.size() * 3 + 9];
		System.out.println(qPoints.length);
		for (int i = 0; i < baseSites.size(); i++) {
			Site currSite = (Site) baseSites.get(i);
			qPoints[i * 3] = currSite.x;
			qPoints[i * 3 + 1] = currSite.z;
			qPoints[i * 3 + 2] = -(currSite.x * currSite.x + currSite.z * currSite.z); // standard half-squared euclidian distance
		}
		// 1
		qPoints[qPoints.length - 9] = -8000D;
		qPoints[qPoints.length - 8] = 0D;
		qPoints[qPoints.length - 7] = -64000000D;
		// 2
		qPoints[qPoints.length - 6] = 8000D;
		qPoints[qPoints.length - 5] = 8000D;
		qPoints[qPoints.length - 4] = -128000000D;
		// 3
		qPoints[qPoints.length - 3] = 8000D;
		qPoints[qPoints.length - 2] = -8000D;
		qPoints[qPoints.length - 1] = -128000000D;

		// prepare quickhull
		QuickHull3D quickHull = new QuickHull3D(qPoints);

		int[][] faces = quickHull.getFaces(QuickHull3D.POINT_RELATIVE + QuickHull3D.CLOCKWISE);
		int artifact = 0;

		// compute dual points
		Corner dualVerts[] = new Corner[faces.length];

		for (int i = 0; i < faces.length; i++) {

			// test if it's the artifact
			if (faces[i][0] >= baseSites.size() && faces[i][1] >= baseSites.size() && faces[i][2] >= baseSites.size())
				artifact = i;

			double x0 = qPoints[faces[i][0] * 3 + 0];
			double y0 = qPoints[faces[i][0] * 3 + 1];
			double x1 = qPoints[faces[i][1] * 3 + 0];
			double y1 = qPoints[faces[i][1] * 3 + 1];
			double x2 = qPoints[faces[i][2] * 3 + 0];
			double y2 = qPoints[faces[i][2] * 3 + 1];

			double v1x = 2 * (x1 - x0);
			double v1y = 2 * (y1 - y0);
			double v1z = x0 * x0 - x1 * x1 + y0 * y0 - y1 * y1;

			double v2x = 2 * (x2 - x0);
			double v2y = 2 * (y2 - y0);
			double v2z = x0 * x0 - x2 * x2 + y0 * y0 - y2 * y2;

			double tmpx = v1y * v2z - v1z * v2y;
			double tmpy = v1z * v2x - v1x * v2z;
			double tmpz = v1x * v2y - v1y * v2x;

			dualVerts[i] = new Corner(tmpx / tmpz, 0.0, tmpy / tmpz);
			if (corners.containsKey(dualVerts[i].toString())) {
				dualVerts[i] = corners.get(dualVerts[i].toString());
				System.out.println("mergedVerts: " + corners.size());
			} else {
				corners.put(dualVerts[i].toString(), dualVerts[i]);
			}
		}

		System.out.println("total mergedVerts: " + corners.size() + "   " + dualVerts.length);

		// create edge/point/face network
		// edges = new float[1][4];
		int edgeCount = 0;
		LinkedArray faceNet = new LinkedArray(faces.length);
		ArrayList<ArrayList<Integer>> pointBuckets = new ArrayList<ArrayList<Integer>>();// IntArray[baseSites.size()];
		for (int i = 0; i < baseSites.size(); i++)
			pointBuckets.add(new ArrayList<Integer>());// new IntArray();

		// discover edges
		Trace.getCurrentMethodName();
		int newCornerCount = 0;
		int reuseCornerCount = 0;
		for (int i = 0; i < faces.length; i++) {

			// bin faces to the points they belong with
			for (int f = 0; f < faces[i].length; f++) {
				if (faces[i][f] < baseSites.size()) {
					pointBuckets.get(faces[i][f]).add(i);
				}
			}

			for (int j = 0; j < i; j++) {
				if (i != artifact && j != artifact && isEdgeShared(faces[i], faces[j])) {

					faceNet.link(i, j);

					Corner newCorner1 = new Corner(dualVerts[i].x, 0, dualVerts[i].z);
					Corner newCorner2 = new Corner(dualVerts[j].x, 0, dualVerts[j].z);

					newCorner1 = corners.get(newCorner1.toString());
					newCorner2 = corners.get(newCorner2.toString());

					Edge newEdge = new Edge();
					newEdge.corner1 = newCorner1;
					newEdge.corner2 = newCorner2;

					edges.put(newEdge.toString(), newEdge);

					newCorner1.neighbors.add(newEdge.corner2);
					newCorner2.neighbors.add(newEdge.corner1);

					edgeCount++;

				}

			}

		}

		System.out.println("new: " + newCornerCount + "    reuse: " + reuseCornerCount);
		Trace.getCurrentMethodName();

		// calculate the region for each point
		regions = new Region[baseSites.size()];
		for (int i = 0; i < baseSites.size(); i++) {
			// IntArray faceOrder = new IntArray(pointBuckets.get(i).size());
			ArrayList<Integer> faceOrder = new ArrayList<Integer>();

			// add coords of the region in the order they touch, starting with
			// the convenient first
			int p = pointBuckets.get(i).get(0);

			while (p >= 0) {

				faceOrder.add(p);

				// find the next coordinate that is in this set that we haven't
				// used yet
				int newP = -1;
				for (int k = 0; k < faceNet.get(p).links.size(); k++) {
					int neighbor = faceNet.get(p).links.get(k);
					if (!faceOrder.contains(neighbor) && pointBuckets.get(i).contains(neighbor)) {
						newP = neighbor;
						break;
					}
				}
				p = newP;

			}

			// turn the coordinates into a polygon
			regions[i] = new Region(pointBuckets.get(i).size());
			for (int f = 0; f < faceOrder.size(); f++) {
				int face = faceOrder.get(f);
				regions[i].addCorner(dualVerts[face]);
			}

			regions[i].site = (Site) baseSites.get(i);
			regions[i].site.region = regions[i];

			ArrayList<Corner> tempCorners = regions[i].getCorners();
			for (int j = 0; j < tempCorners.size(); j++) {
				Edge tempEdge = new Edge();
				tempEdge.corner1 = tempCorners.get(j);
				if (j < tempCorners.size() - 1) {
					tempEdge.corner2 = tempCorners.get(j + 1);
				} else {
					tempEdge.corner2 = tempCorners.get(0);
				}
				Edge tempEdge2 = edges.get(tempEdge.toString());
				if (tempEdge2 == null) {
					edges.put(tempEdge.toString(), tempEdge);
					tempEdge2 = tempEdge;
				}
				if (tempEdge2.site1 == null) {
					tempEdge2.site1 = regions[i].site;
				} else if (tempEdge2.site2 == null) {
					tempEdge2.site2 = regions[i].site;
				}
				regions[i].addEdge(tempEdge2);
				tempCorners.get(j).isBorder = tempCorners.get(j).isBorder || regions[i].site.isBorder;
			}

			regions[i].pointNormalsUp();
		}

	}

	public Region[] getRegions() {
		return regions;
	}

	public ArrayList<Edge> getEdges() {
		ArrayList<Edge> edgeList = new ArrayList<Edge>();

		for (Map.Entry<String, Edge> entry : edges.entrySet()) {
			Edge currEdge = (Edge) entry.getValue();
			edgeList.add(currEdge);
		}

		return edgeList;
	}

	public void relax(int steps) {
		Trace.getCurrentMethodName();
		for (int currStep = 0; currStep < steps; currStep++) {
			for (int i = 0; i < regions.length; i++) {
				Region currRegion = regions[i];
				Site currSite = regions[i].site;

				if (!currSite.isBorder) {
					Site averageSite = new Site();
					for (int j = 0; j < currRegion.vertCount(); j++) {
						Vertex currVert = currRegion.getVerts().get(j);
						averageSite.x += currVert.x;
						averageSite.y += currVert.y;
						averageSite.z += currVert.z;
					}
					averageSite.x /= currRegion.vertCount();
					averageSite.y /= currRegion.vertCount();
					averageSite.z /= currRegion.vertCount();

					sites.set(i, averageSite);
				}
			}
			generate(sites);
		}
	}

	protected boolean isEdgeShared(int face1[], int face2[]) {
		for (int i = 0; i < face1.length; i++) {
			int cur = face1[i];
			int next = face1[(i + 1) % face1.length];
			for (int j = 0; j < face2.length; j++) {
				int from = face2[j];
				int to = face2[(j + 1) % face2.length];
				if (cur == from && next == to || cur == to && next == from)
					return true;
			}
		}
		return false;
	}

	public void populateSiteLinks() {
		Trace.getCurrentMethodName();

		delaunay.generateDelaunay(sites);

		for (int i = 0; i < sites.size(); i++) {
			Site currSite = (Site) sites.get(i);
			ArrayList<Integer> links = delaunay.getLinked(i);
			currSite.links = new ArrayList<Site>();

			for (int j = 0; j < links.size(); j++) {
				Site nextSite = (Site) sites.get(links.get(j));
				currSite.links.add(nextSite);
				//currSite.region.neighbors.add(nextSite.region);
			}
		}
	}

	public void populateRegionNeighbors() {
		for (Map.Entry<String, Edge> entry : edges.entrySet()) {
			Edge currEdge = (Edge) entry.getValue();
			if (currEdge.site1 != null && currEdge.site2 != null) {
				currEdge.site1.region.neighbors.add(currEdge.site2.region);
				currEdge.site2.region.neighbors.add(currEdge.site1.region);
			}
		}
	}
}
